package com.canopys.study.open.test.algorithm.tree;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 21:30 2019/8/18
 * @Modified By:
 */
public class BSortTree {

    // 递归插入
    public static TreeModel insert(TreeModel root, int data) {
        if (null == root) {
            root = new TreeModel();
            root.setData(data);
            root.setRchild(null);
            root.setLchild(null);
            return root;
        }

        if (root.getData() > data) {
            root.setLchild(insert(root.getLchild(), data));
        } else if (root.getData() < data) {
            root.setRchild(insert(root.getRchild(), data));
        } else {
            throw new RuntimeException("error");
        }
        return root;
    }

    // 非递归
    public static TreeModel insertTravsersa(TreeModel root, int data) {
        TreeModel in = new TreeModel();
        in.setData(data);
        in.setLchild(null);
        in.setRchild(null);
        
        if (null == root) {
            root = in;
            return root;
        }

        TreeModel pre = null;
        TreeModel tmp = root;
        while (null != tmp) {
            pre = tmp;
            if (tmp.getData() > data) {
                tmp = tmp.getLchild();
            } else if (tmp.getData() < data) {
                tmp = tmp.getRchild();
            } else {
                throw new RuntimeException("error");
            }
        }

        if (pre.getData() > data) {
            pre.setLchild(in);
        } else if (pre.getData() < data) {
            pre.setRchild(in);
        }

        return root;
    }

    public static boolean delete(TreeModel root, int data) {
        if (null == root) {
            return false;
        }

        if (root.getData() == data) {
            root = null;
            return true;
        }

        TreeModel pre = root;
        TreeModel tmp = root;
        while (null != tmp) {
            if (tmp.getData() == data) {
                pre.setLchild(tmp.getLchild());
                pre.setRchild(tmp.getRchild());
                return true;
            } else if (tmp.getData() > data) {
                pre = tmp;
                tmp = tmp.getLchild();
            } else {
                pre = tmp;
                tmp = tmp.getRchild();
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeModel root = null;
        for (int i = 0; i < 10; i++) {
            //root = insert(root, i);
            root = insertTravsersa(root, i);
        }
        TreeTest.inOrder(root);

        System.out.println();
        System.out.println("是否删除了元素 : " + delete(root, 1) );
        TreeTest.inOrder(root);
    }
}
